백준 2252번

오늘 풀어본 문제는 백준의 2252번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$N$ 명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 $N$ $(1 \le N \le 32,000)$, $M$ $(1 \le M \le 100,000)$ 이 주어진다. $M$ 은 키를 비교한 회수이다. 다음 $M$ 개의 줄에는 키를 비교한 두 학생의 번호 $A, B$ 가 주어진다. 이는 학생 $A$ 가 학생 $B$ 의 앞에 서야 한다는 의미이다.

학생들의 번호는 $1$ 번부터 $N$ 번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

풀이과정

1번째 시도

이 문제를 보고 예전에 본 적 있던 ‘위상정렬’ 이라는 겻을 이용해야 한다는 것을 알 수 있었다. 우선 queue 를 이용하여 구현을 시도하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N+1);
    vector<int> entryDeg(N+1, 0);
    vector<bool> visited(N+1, false);

    for (int i=0; i<M; i++) {
        int A, B;
        cin >> A >> B;

        graph[A].emplace_back(B);
        entryDeg[B]++;
    }

    queue<int> q;
    for (int i=1; i<=N; i++) {
        if (entryDeg[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        if (visited[curr]) {
            continue;
        }
        else if (entryDeg[curr] != 0) {
            q.push(curr);
        }
        else {
            visited[curr] = true;
            for (auto next : graph[curr]) {
                entryDeg[next]--;
                q.push(next);
            }
        }

        cout << curr << " ";
    }

    return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

2번째 시도

틀린 이유로 우선 생각해본 것은 위상정렬이 제대로 구현되지 않았기 때문이라 생각하였고, 위상정렬이 이루어지는 순서에 대해서 생각해본 결과, visited 변수가 필요없다는 것을 알 수 있었다.

어떤 정점의 진입 차수가 $0$ 인 경우에만 해당 정점을 방문해야 하고, 문제의 조건 자체가 DAG 를 형성하기 때문에 현재 정점에서 인접한 정점들을 확인했을 때, 그 정점들의 진입 차수가 $0$ 이 되는 것이 아닌 이상은 다른 정점들에서도 확인을 거쳐야 하는 것이었다.

쉽게 말하자면, entryDeg 가 이미 visited 와 유사한 역할을 수행하고 있었다는 것이다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N+1);
    vector<int> entryDeg(N+1, 0);

    for (int i=0; i<M; i++) {
        int A, B;
        cin >> A >> B;

        graph[A].emplace_back(B);
        entryDeg[B]++;
    }

    queue<int> q;
    for (int i=1; i<=N; i++) {
        if (entryDeg[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (auto next : graph[curr]) {
            entryDeg[next]--;
            if (entryDeg[next] == 0) {
                q.push(next);
            }
        }

        cout << curr << " ";
    }

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

오늘 풀었던 문제는 조금 전에도 말했다시피 위상정렬을 이용한 문제인데, ‘위상’ 이라는 단어가 들어가 있는 것을 확인할 수 있다. 요즘 위상수학 공부를 좀 하고 있는데, 앞으로 배우게 될 내용과 관련이 있을지 조금 궁금해지게 되었다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/2252

← Previous Post Next Post →